package com.itheima.test;

import java.util.Arrays;

public class Demo_004 {
    //快速排序;
    public static void main(String[] args) {
        //1，从右开始找比基准数小的
        // 2，从左开始找比基准数大的
        // 3，交换两个值的位置
        // 4，红色继续往左找，蓝色继续往右找，直到两个箭头指向同一个索引为止
        // 5，基准数归位
        int[] arr = {132, 464, 56, 34, 1, 346, 7};
        int left = 0;
        int right = arr.length - 1;
        quickSort(arr, left, right);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int left, int right) {
        //递归的出口;
        if (left > right) {
            return;
        }
        //定义一个临时变量,方便一会基准数归位;
        int left0 = left;
        //计算出基准数;
        int number = arr[left];
        while (left != right) {
            while (arr[right] >= number && right > left) {
                right--;
            }
            while (arr[left] <= number && right > left) {
                left++;
            }
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //基准数归位;
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

        quickSort(arr,left0,left-1);
        quickSort(arr,left+1,arr.length-1);
    }
}
